#![feature(min_const_generics)]

use integer::prelude::*;
use std::io;
use std::io::prelude::*;
use std::time::Instant;

const ROUNDS: u32 = 10;

const MOD_BITS: u32 = 2048;
const EXP_BITS: u32 = 240;
const TEST_SIZE: u32 = 4096;

/*
 * P75 = 664 85659796 45277755 9123_2190 67300940
 *  51844953 78793489 59444670 35675855 57440257
 * from the factors of 5^128+4^128
 */
const PRIME32: [u8; 32] = [
	0x01, 0x67, 0x19, 0xAD, 0xE5, 0xE7, 0x39, 0xAD, 0x44, 0x1B, 0xEA, 0x3C, 0x3F, 0x16, 0xD4, 0xA0,
	0xE2, 0xBC, 0x7D, 0x31, 0x4E, 0x0F, 0xE6, 0x73, 0xEB, 0x03, 0x30, 0xD3, 0xA5, 0x4B, 0x78, 0x01,
];

const SMALL_PRIME: [u64; 15] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 41, 43];

fn write_equal_n<const N: usize>(lhs: [&str; N], rhs: [String; N]) {
	lhs.iter().zip(rhs.iter()).for_each(|pair| {
		let (lexp, rexp) = pair;
		println!("{} = {}", lexp, rexp);
	});
}

fn write_equal(lexp: &str, rexp: String) {
	println!("{} = {}", lexp, rexp);
}

struct Tiktok<const N: usize>(Instant, [u128; N]);

impl<const N: usize> Tiktok<N> {
	pub fn tik(&mut self) {
		self.0 = Instant::now();
	}

	pub fn tok(&mut self, i: usize) {
		self.1[i] += self.0.elapsed().as_nanos();
	}

	pub fn clear(&mut self, i: usize) {
		self.1[i] = 0;
	}

	pub fn time(&self, i: usize) -> f64 {
		self.1[i] as f64 / 1e6
	}
}

#[test]
fn sainty() {
	/* inintialize */
	let ref zero = Integer::zero();
	let ref one = Integer::one();
	let ref two = Integer::two();

	/* The largest known non-Mersenne prime, discovered in November 2016.
	 * 10223 * 2**31172165 + 1
	 */
	let prime_nm: Integer = Integer::try_convert(10223u64, 1)
		.multiply_with(&one.shift_left(31172165))
		.add_with(&one);
	let ref a = Integer::try_convert(PRIME32, 1);
	let ref b = a - one;
	let mut timer = Tiktok(Instant::now(), [0u128; 8]);

	println!("Testing modexp with a known prime. All results should be 1.");
	write_equal_n(["p  ", "p-1"], [a.hex(), b.hex()]);

	let z = two.powmod(&b, &a);
	write_equal("2^(p-1) mod p", z.hex());

	for _ in 0..10 {
		let rnd = Integer::random(b.bits() - 1);
		let z = rnd.powmod(&b, &a);
		write_equal_n(["rnd", "rnd^(p-1) mod p"], [rnd.hex(), z.hex()]);
	}

	println!("\nTiming test start. We will test operators and prime tests. ");

	// timer.tik();
	// let check = prime_nm.is_prime(100);
	// timer.tok(0);
	// println!(
	// 	"the prime number is tested {} as a prime, time: {} millis",
	// 	check,
	// 	timer.time(0)
	// );
	// timer.clear(0);

	for _ in 0..25 {
		let ref e = Integer::random(MOD_BITS); /* Base */
		let ref f = Integer::random(EXP_BITS); /* Exponent */
		let ref g = Integer::random(MOD_BITS); /* Modulus */
		let ref h = Integer::random(MOD_BITS); /* Base2 */

		timer.tik();
		e + h;
		timer.tok(0);

		timer.tik();
		e - h;
		timer.tok(1);

		timer.tik();
		e * h;
		timer.tok(2);

		timer.tik();
		e / g;
		timer.tok(3);

		let r = rand::random::<u32>() & 0x3ff;
		timer.tik();
		e ^ r;
		timer.tok(4);

		timer.tik();
		e.gcd(h);
		timer.tok(5);

		timer.tik();
		e.powmod(f, g);
		timer.tok(6);

		timer.tik();
		e.compare(h);
		timer.tok(7);
	}

	println!(
		"add:     \t{}\nsubtract:\t{}\nmultiply:\t{}\ndivide:  \t{}\npower:   \t{}\ngcd:     \t{}\npowmod:  \t{}\ncompare: \t{}\n\n",
		timer.time(0) / 25.,
		timer.time(1) / 25.,
		timer.time(2) / 25.,
		timer.time(3) / 25.,
		timer.time(4) / 25.,
		timer.time(3) / 25.,
		timer.time(6) / 25.,
		timer.time(7) / 25.
	);

	for j in 1..=ROUNDS {
		// Integer v, w, x, y, z;
		// Integer d, e, f, g, h;
		// pInteger rnd, trans;
		/* Do the tests for lots of different number sizes. */
		for i in 1..=TEST_SIZE / 2 {
			/* Make a random number i words long */
			let ref d = Integer::random(i);
			assert!(d.bits() == i);

			/* Checl lbnCmp - does a == a? */
			if !(d == d) {
				write_equal_n(["a", "(a <=> a)"], [d.hex(), (d == d).to_string()]);
				println!("------------------------");
				panic!("equal");
			}

			let ref e = d.clone();

			/* Check that the difference, after copy, is good. */
			if !(d == e) {
				write_equal_n(
					["a", "b", "(a <=> b)"],
					[d.hex(), e.hex(), (d == e).to_string()],
				);
				println!("------------------------");
				panic!("clone");
			}

			/* Generate a non-zero random t */
			let mut t = 0u64;
			while t == 0 {
				t = rand::random::<u64>();
			}

			let ref f = int!(t);

			/*
				* Add t to A.  Check that:
				* - addWord works fine,
				* - compare works in both directions, and
				* - A + t is greater than A.
				*/
			let ref y = d + f;
			if (!(d < y) && !(y < d)) || !(y > d) {
				write_equal_n(
					["a", "t", "c = a + t", "(a <=> c)", "(c <=> a)"],
					[
						d.hex(),
						f.hex(),
						y.hex(),
						(d == y).to_string(),
						(y == d).to_string(),
					],
				);
				println!("------------------------");
				panic!("add and greater");
			}

			/* Subtract t again */
			let ref z = d - f;
			if (!(d < z) && !(z < d)) || !(z < d) {
				write_equal_n(
					["a", "t", "c = a - t", "(a <=> c)", "(c <=> a)"],
					[
						d.hex(),
						f.hex(),
						z.hex(),
						(d == z).to_string(),
						(z == d).to_string(),
					],
				);
				println!("------------------------");
				panic!("subtract less");
			}

			/* add or subtract -t to A, make sure:
			 * - negate is right,
			 * - add and subtract negative number works fine.
			 */
			let ref h = f.negate();
			let ref v = d + h;
			let ref w = d - h;
			if !(y == w) || !(z == v) {
				write_equal_n(
					[
						"a",
						"t",
						"c = a + t",
						"d = a - t",
						"f = a + -t",
						"e = a - -t",
						"(c <=> e)",
						"(d <=> f)",
					],
					[
						d.hex(),
						f.hex(),
						y.hex(),
						z.hex(),
						v.hex(),
						w.hex(),
						(y == w).to_string(),
						(z == v).to_string(),
					],
				);
				println!("------------------------");
				panic!("negate");
			}

			/* Generate a random B */
			let ref e = Integer::random(i);

			let ref y = d + e;
			let ref z = y - e;

			if !(z == d) {
				write_equal_n(
					["a", "b", "a += b", "a -= b", "(a <=> a)"],
					[d.hex(), e.hex(), y.hex(), z.hex(), (z == y).to_string()],
				);
				println!("------------------------");
				panic!("random add and subtract");
			}

			/* D = B * t. Check that:
			 * - operator priority.
			 * - mulWord works fine.
			 */
			let ref g = int!(t / 2);
			let ref y = match f.is_odd() {
				true => e * g + e * g + e,
				false => e * g + e * g,
			};
			let ref z = e * f;
			if !(y == z) {
				write_equal_n(
					[
						"a",
						"t",
						"c = b * (t/2) + b * (t/2)",
						"d = b * t",
						"(c <=> d)",
					],
					[e.hex(), f.hex(), y.hex(), z.hex(), (y == z).to_string()],
				);
				println!("------------------------");
				panic!("operator priority and wulword");
			}

			/* Does Mul work both ways symmetrically */
			let ref y = d * e;
			let ref z = e * d;
			if !(y == z) {
				write_equal_n(
					["a", "b", "c = a * b", "d = b * a", "(c <=> d)"],
					[d.hex(), e.hex(), y.hex(), z.hex(), (y == z).to_string()],
				);
				println!("------------------------");
				panic!("symmetric multiply");
			}

			/* Check multiplication modulo some small things */
			/* 30030 = 2*3*5*11*13 */
			let ref g = int!(30030u64);
			let ref z = y % g;
			for l in 0..15 {
				let ref h = int!(SMALL_PRIME[l]);
				let ref v = y % h;
				let ref w = d % h;
				let ref x = e % h;
				if !(v == ((w * x) % h)) {
					write_equal_n(
						[
							"a",
							"b",
							"c",
							"d = a % c",
							"e = b % c",
							"f = (a * b) % c",
							"(f <=> d * e (% c))",
						],
						[
							d.hex(),
							e.hex(),
							h.hex(),
							w.hex(),
							x.hex(),
							v.hex(),
							(v == ((w * x) % h)).to_string(),
						],
					);
					println!("------------------------");
					panic!("module");
				}
				/* Verify that (C % 30030) % m == C % m */
				if SMALL_PRIME[l] <= 13 && (v != (z % h)) {
					write_equal_n(
						["a*b % 30030", "(a*b % 30030) % m", "a*b % m"],
						[z.hex(), (z % h).hex(), v.hex()],
					);
					println!("------------------------");
					panic!("module twice");
				}
			}

			/* Generate an F less than A and B */
			let ref f = match i > 1 {
				true => Integer::random(i - 1),
				false => Integer::zero(),
			};

			/* Add F to D (remember, D = A*B) */
			let ref y = y + f;

			/*
				* Divide by A and check that quotient and remainder
				* match (remainder should be F, quotient should be B)
				*/
			let ref v = y / d;
			let ref w = y % d;
			if !(v == e) || !(w == f) {
				write_equal_n(
					[
						"a",
						"b",
						"c",
						"g = a * b + c",
						"h = g / a",
						"i = g % a",
						"(h <=> b)",
						"(i <=> c)",
					],
					[
						d.hex(),
						e.hex(),
						f.hex(),
						y.hex(),
						v.hex(),
						w.hex(),
						(v == e).to_string(),
						(w == f).to_string(),
					],
				);
				println!("------------------------");
				panic!("division");
			} // w == (f % d)

			/* Divide by B and check similarly */
			let ref v = y / e;
			let ref w = y % e;
			if !(v == d) || !(w == f) {
				write_equal_n(
					[
						"a",
						"b",
						"c",
						"g = a * b + c",
						"h = g / b",
						"i = g % b",
						"(h <=> a)",
						"(i <=> c)",
					],
					[
						d.hex(),
						e.hex(),
						f.hex(),
						y.hex(),
						v.hex(),
						w.hex(),
						(v == d).to_string(),
						(w == f).to_string(),
					],
				);
				println!("------------------------");
				panic!("symm-division");
			} // w == (f % d)

			/* Check that A*A == A^2 */
			let ref y = d * d;
			let ref z = d ^ 2;
			if !(y == z) {
				write_equal_n(
					["a", "b = a*a", "c = a^2", "(b <=> c)"],
					[d.hex(), y.hex(), z.hex(), (y == z).to_string()],
				);
				println!("------------------------");
				panic!("square");
			}

			/* Compute a GCD */
			let ref g = d.gcd(e);

			/* Approximate check that the GCD came out right */
			for l in 0..15 {
				let ref h = int!(SMALL_PRIME[l]);
				let ref x = g % h;
				let ref y = d % h;
				let ref z = e % h;
				if !((x == zero) == ((y == zero) && (z == zero))) {
					write_equal_n(
						["a", "b", "c = gcd(a,b)", "d"],
						[d.hex(), e.hex(), g.hex(), h.hex()],
					);
					println!("------------------------");
					panic!("gcd");
				}
			}

			/*
			 * Do some Montgomery operations
			 * Start with A > B, and also place a copy of B into C.
			 * Then make A odd so it can be a Montgomery modulus.
			 */
			let (mut d, e) = match d < e {
				true => (e.clone(), d),
				false => (d.clone(), e),
			};

			if !d.is_odd() {
				d = d + one;
			}

			/* E = B^5 (mod A), no Montgomery ops */
			let ref w = e ^ 5;
			let ref x = w % &d;

			/* D = B^5, using ExpMod */
			let ref f = int!(5u64);
			let ref y = e.powmod(f, &d);

			if !(x == y) {
				write_equal_n(
					["a", "b", "c = b ^ 5", "d = c % a", "e = b.powmod(5, a)"],
					[d.hex(), e.hex(), w.hex(), x.hex(), y.hex()],
				);
				println!("------------------------");
				panic!("modpow");
			}
			print!("\rtesting bit {}", i);
			io::stdout().flush().ok().expect("could not flush");
		} /* for (i) */
		print!("\rround {} passed.  \n", j);
		io::stdout().flush().ok().expect("could not flush");
	} /* for (j) */
	println!(
		"{} iterations of up to {} 32-bit words completed.\n",
		ROUNDS,
		TEST_SIZE / 2,
	);
}
